<!doctype html>
<html><head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
    <title>寻径算法</title>
    <meta name="description" content="">
    <meta name="keywords" content="">
    <link href="" rel="stylesheet">
    <style>
        .button{
            width: 531px;
            margin: 10px auto;
        }
        table{
            border-collapse: collapse;
            width: 531px;
            margin: 0 auto;
        }
        td{
            width: 50px;
            height: 50px;
            border:1px solid orange;
        }
        td.start{
            background: url(cat.jpg) no-repeat center center;
            background-size: 100% 100%;
        }
        td.end{
            background: url(fish.png) no-repeat center center;
            background-size: 100% 100%;
        }
        td.current{
            background: skyblue;
        }
        td.path{
            background: url(foot.jpg) no-repeat center center;
            background-size: 100% 100%;
        }
        td.block{
            background: url(block.gif) no-repeat center center;
            background-size: 80% 80%;
        }
    </style>
</head>
<body>
<div class="button">
    <button onclick="javascript:console.time('t');searchRoad();console.timeEnd('t');">去吃鱼啦</button>
</div>
<script type="text/javascript">


    /**
    一直想用js自己写写游戏啥的，所以之前花了些时间去研究寻路算法，在寻路算法中说的比较多的估计就是A*了，但是那时候觉得A*不是很好理解，没弄明白，所以我尝试了另外一种寻路算法，点击这里穿越，这种算法确实能准确的找到一条可行的路线，但也仅仅是可行，因为这种算法找出来的路线和最佳路线就完全扯不上边，本来可以走更短的距离到达终点，却非要绕一大圈，肯定不乐意了。所以我又回去折腾了一下寻径算法。

     其实A*寻路算法就好比是上面那种比较蠢的算法的升级版吧，在那个算法的基础上引入了F,G,H这三个东西，那么他们是干什么的呢？

     首先我们需要知道一个公式：F = G + H

     其中，F 是从起点经过该点到终点的总路程，G 为起点到该点的“已走路程”，H 为该点到终点的“预计路程”。

     寻路步骤：

     1. 从起点A开始, 把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格的列表.

     2. 寻找起点A周围可以到达的方格, 将它们放入"开启列表", 并设置它们的"父方格"为A.

     3. 从"开启列表"中删除起点 A, 并将起点 A 加入"关闭列表", "关闭列表"中存放的都是不需要再次检查的方格

     4. 从 "开启列表" 中选择 F 值最低的方格 C (绿色起始方块 A 右边的方块),检查它所有相邻并且可以到达 (障碍物和 "关闭列表" 的方格都不考虑) 的方格. 如果这些方格还不在 "开启列表" 里的话, 将它们加入 "开启列表", 计算这些方格的 G, H 和 F 值各是多少, 并设置它们的 "父方格" 为 C.

     5. 如果某个相邻方格 D 已经在 "开启列表" 里了, 检查如果用新的路径 (就是经过C 的路径) 到达它的话, G值是否会更低一些, 如果新的G值更低, 那就把它的 "父方格" 改为目前选中的方格 C, 然后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, H 值是不变的). 如果新的 G 值比较高, 就说明经过 C 再到达 D 不是一个明智的选择, 因为它需要更远的路, 这时我们什么也不做.

     就这样, 我们从 "开启列表" 找出 F 值最小的, 将它从 "开启列表" 中移掉, 添加到 "关闭列表". 再继续找出它周围可以到达的方块, 如此循环下去...

     那么什么时候停止呢? —— 当我们发现 "开始列表" 里出现了目标终点方块的时候, 说明路径已经被找到.

     最后以终点为起点通过 "父方块" 可以依次索引到最初的 "起始方块", 这样就得到了路径.
     */
    var rows = 10,cols =10;
    var map = multiArray(rows,cols),elems = multiArray(rows,cols);
    var start = {
        x: 0,
        y: 0
    };
    var end = {
        x: 9,
        y: 9
    };
    var table = document.createElement("table");
    for(var i=0,l=map.length;i<l;i++){
        var tr = document.createElement("tr");
        for(var j=0,ll=map[i].length;j<ll;j++){
            var td = document.createElement("td");
            if(i==start.y&&j==start.x){
                td.className = "start";
            }
            if(i==end.y&&j==end.x){
                td.className = "end";
            }
            elems[j][i] = tr.appendChild(td);
            (function(i,j){
                td.onclick = function(){
                    clearPath();
                    if(elems[j][i].className=="block"){
                        elems[j][i].className = "";
                        map[j][i] = 0;
                    }else if(!elems[j][i].className){
                        elems[j][i].className = 'block';
                        map[j][i] = 1;
                    }
                }
            })(i,j);
        }
        table.appendChild(tr);
    }
    document.body.appendChild(table);
    function multiArray(rows,cols){
        var a = new Array(rows);
        for(var i=0,l=a.length;i<l;i++){
            a[i] = new Array(cols);
            for(var j=0;j<cols;j++){
                a[i][j] = 0;
            }
        }
        return a;
    }
    function clearPath(){
        for(var i=0,l=map.length;i<l;i++){
            for(var j=0,ll=map[i].length;j<ll;j++){
                if(elems[j][i].className=="path"){
                    elems[j][i].className = "";
                }
            }
        }
    }

    function searchRoad() {
        var openList = [], closeList = [],
            result = [], result_index;
        openList.push({
            x: start.x,
            y: start.y,
            G: 0
        });
        while(!(result_index=existList({x: end.x, y: end.y}, openList))){
            var currentPoint = openList.pop();
            closeList.push(currentPoint);
            var sourroundPoint = getSurroundPoint(currentPoint);
            sourroundPoint.map(function(item, index) {
                if (item.x >= 0 &&
                    item.x < cols &&
                    item.y >= 0 &&
                    item.y < rows &&
                    map[item.x][item.y] !== 1 &&
                    !existList(item, closeList)) {
                    var g = currentPoint.G + ((item.x - currentPoint.x) * (item.y - currentPoint.y) === 0 ? 10 : 14);
                    if (!existList(item, openList)) {
                        item['H'] = Math.abs(end.x - item.x) * 10 + Math.abs(end.y - item.y) * 10;
                        item['G'] = g;
                        item['F'] = item.G + item.H;
                        item['parent'] = currentPoint;
                        openList.push(item);
                    }
                }
            });
            if (openList.length === 0) {
                alert('没有可用路径');
                break;
            }
            openList.sort(sortF);
        };

        if (result_index) {
            var currentObj = openList[result_index];
            while(currentObj.x !== start.x || currentObj.y != start.y){
                result.unshift({
                    x: currentObj.x,
                    y: currentObj.y
                });
                currentObj = currentObj.parent;
            };
        }
        for(var i=0,l=result.length;i<l;i++){
            if(result[i].x==end.x&&result[i].y==end.y) continue;
            elems[result[i].x][result[i].y].className = 'path';
        }
        return result;
    }
    //用F值对数组排序
    function sortF(a,b){
        return b.F- a.F;
    }
    function getSurroundPoint(currentPoint) {
        var x = currentPoint.x, y = currentPoint.y;
        return [
            {x:x-1,y:y-1},
            {x:x,y:y-1},
            {x:x+1,y:y-1},
            {x:x+1,y:y},
            {x:x+1,y:y+1},
            {x:x,y:y+1},
            {x:x-1,y:y+1},
            {x:x-1,y:y}
        ];
    }
    function existList(point,list) {
        for(var i in list) {
            if(point.x==list[i].x && point.y==list[i].y) {
                return i;
            }
        }
        return false;
    }
</script><table><tr><td class="start"></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td class="end"></td></tr></table>


</body></html>